#include <iostream>
#include <cstdlib>

// 传入下标而非指针
void recursion(int **thefts,int r_s,int r_e,int c_s,int c_e)
{
    // 原来是判空条件有问题？？？
    if (r_e-r_s == 1&&c_e-c_s ==1)
    {
        thefts[r_s][c_s] = 0;
        return ;
    }

    // 先处理第二象限
    int second_r = (r_s+r_e)/2;
    int second_c = (c_s+c_e)/2;

    for (int i = r_s;i < second_r+1;i++)
    {
        for(int j = c_s;j < second_c+1;j++)
        {
            thefts[i][j] = 0;
        }
    }

    // 递归处理第一象限和第三象限
    recursion(thefts,r_s,second_r,second_c+1,c_e);
    recursion(thefts,second_r+1,r_e,c_s,second_c);
    return ;
}

int main()
{
    // 计算总大小 total
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    int n;
    std::cin>>n;

    int total = 1;
    for (int i = 0;i < n;i ++)
    {
        total*= 2;
    }

    // 动态分配二维数组
    int ** thefts = (int**)malloc(total*sizeof(int*));
    // 仍需使用for循环为每一行分配空间
    for (int i = 0;i < total;i ++)
    {
        thefts[i] = (int*)malloc(total*sizeof(int));
    }

    // 初始化二维数组
    for (int i = 0;i < total;i ++)  
    {
        for (int j = 0;j < total;j ++)
        {
            thefts[i][j] =1;
        }
    }

    // 这里需要使用下标说话而非指针
    // 传参时要传起始位置和终止位置
    recursion(thefts,0,total-1,0,total-1);
    
    // 输出结果
    for (int i = 0;i < total;i ++)  
    {
        for (int j = 0;j < total;j ++)
        {
            std::cout<<thefts[i][j];
        }
        std::cout<<"\n";
    }

    // 释放内存
    for (int i = 0;i < total;i ++)
    {
        free(thefts[i]);
        thefts[i] = nullptr;
    }
    free(thefts);
    thefts = nullptr;

    return 0;
}

// 基本思路是:
// 先让二维数组整个初始化为1
// 每次使用嵌套循环将左上部分全变为0
// 然后对第一象限部分和第三象限部分调用递归
// 递归终止条件为起始位置与终止位置差1
// 此时将指针指向位置改为0
// 是不是r_s和r_e出了问题？？？
